package com.leetcode.根据数据结构分类.栈;

/**
 * @author: ZhouBert
 * @date: 2020/11/20
 * @description:
 * https://leetcode-cn.com/problems/score-of-parentheses/
 */
public class B_856_括号的分数 {

	/**
	 * (()(()))
	 * 经过分析了以后，这道题必须得有递归：因为每一类都有嵌套
	 *--
	 * 使用了递归的方案求解，但是对于 第三类的感觉相当笨拙！
	 * --
	 * 如果是用栈，该如何求解呢？
	 *
	 * @param S
	 * @return
	 */
	public static int scoreOfParentheses(String S) {

		char[] chars = S.toCharArray();
		return score(chars, 0, chars.length - 1);


		//判断第三类，包围的情况-> 最后得出幂次+ 接下来判断第二类时的数组长度


		//判断第二类
	}

	private static int score(char[] chars, int begin, int end) {
		//判断第一类，也就是递归的终点！
		if (begin + 1 == end) {
			return 1;
		}
		int sum = 0;

		//1.判断第三类//当我发现原来对于第三类的判断不准确的时候，我迷茫了！
		//需要修正判断：需要先剔除最外面的
		int num3 = 0;
		int size = ((end - begin + 1) >> 1) + begin;
		for (int i = begin + 1, j = end - 1; i < size; i++, j--) {
			boolean flag = true;
			if (chars[i] == '(' && chars[j] == ')') {
				//当作只是其中一个条件
				//再判断 ) 是否曾经大于 ( 的个数
				int temp = 0;
				for (int k = i; k <= j; k++) {
					if (chars[k] == '(') {
						temp++;
					} else {
						temp--;
					}
					if (temp < 0) {
						flag = false;
						break;
					}
				}
			} else {
				flag = false;
			}
			if (flag) {
				num3++;
				begin++;
				end--;
			} else {
				break;
			}
		}
		//针对 (()) 的情况，需要马上返回结果！
		if (begin + 1 == end) {
			return (int) Math.pow(2, num3);
		}


		//2.判断第二类
		// 找到分隔点
		int leftNum = 0;
		int rightNum = 0;
		int bIndex = begin;
		for (int i = begin; i <= end; i++) {
			//等待下一次 leftNum == rightNum 时
			if (chars[i] == '(') {
				leftNum++;
			}
			if (chars[i] == ')') {
				rightNum++;
			}
			//找到分割点
			if (leftNum == rightNum) {
				sum += score(chars, bIndex, i);
				bIndex = i + 1;
			}
		}
		sum = sum * (int) Math.pow(2, num3);
		return sum;
	}

	public static void main(String[] args) {
		String str = "(()(()))";
		str = "()()()";
		str = "(()(()))";
		str = "(())";
		str = "(())(())";
		int res = scoreOfParentheses(str);
		System.out.println(res);
	}

}
